One feature of object oriented programming (e.g., using Java) is its garbage-collected heap, which takes care of freeing dynamically allocated memory that is no longer referenced. For example, the Java Virtual Machine's (JVM's) heap stores all objects created by an executing Java program. Objects are created by Java's “new” operator, and memory for new objects is allocated on the heap at run time.
Garbage Collection is the process of automatically freeing objects that are no longer referenced by the program. This frees the programmer from having to keep track of when to free allocated memory, thereby preventing many potential bugs. When an object is no longer referenced by the program, the heap space it occupies must be recycled so that the space is available for subsequent new objects. The garbage collector must determine which objects are no longer referenced by the program and make available the heap space occupied by such unreferenced objects (e.g., free the unreferenced objects). In addition to freeing unreferenced objects, a garbage collector may also combat heap fragmentation. Heap fragmentation occurs through the course of normal program execution. New objects are allocated, and unreferenced objects are freed such that free blocks of heap memory are left in between blocks occupied by live objects. Requests to allocate new objects may have to be filled by extending the size of the heap even though there is enough total unused space in the existing heap. This will happen if there is not enough contiguous free heap space available into which the new object will fit. On a virtual memory system, the extra paging required to service an ever-growing heap can degrade the performance of the executing program.
A potential disadvantage of a garbage-collected heap is that it adds an overhead that can affect program performance. For example, the JVM has to keep track of which objects are being referenced by the executing program, and finalize and free unreferenced objects on the fly. This activity will likely require more central processing unit (CPU) time than would have been required if the program explicitly freed unnecessary memory. In addition, programmers in a garbage-collected environment have less control over the scheduling of CPU time devoted to freeing objects that are no longer needed.
A garbage collector performs several tasks. These tasks may included, for example, detecting garbage objects, reclaiming the heap space used by the garbage objects, and then making this space available to the program. Garbage detection is ordinarily accomplished by defining a set of roots and determining reachability from the roots. An object is reachable if there is some path of references from the roots by which the executing program can access the object. The roots are accessible to the program. Any objects that are reachable from the roots are considered live. Objects that are not reachable are considered garbage, because they can no longer affect the future course of program execution.
The heap also maintains a pointer which will indicate where the next object is to be allocated within the heap. Initially, the pointer is set to the base address of the reserved address region. When a new object is created with the new operator it will make sure that the bytes required for the new object are available on heap. The heap detects this by adding the size of the new object to heap pointer. If a pointer is beyond the end of the address space region, then the heap is full and a collection must be performed.
When a garbage collector begins a garbage collection cycle, it is unknown which objects in the heap are garbage objects. The garbage collector starts traversing the roots and building a graph of all objects reachable from the roots. Once all the roots have been checked, the garbage collector's graph contains the set of all objects that are somehow reachable from the application's roots. Any objects that are not in the graph are not accessible by the application, and are therefore considered garbage.
Garbage collectors that move objects concurrently with a mutator thread (e.g., a thread that performs application processing, as distinct from garbage collection) require a read barrier to ensure that a mutator thread cannot obtain object references that are unknown to the garbage collector. There are several ways of employing a read barrier: either by adding inline instructions, use of dedicated read-barrier assist logic in the processor, or by leveraging the operating system's existing memory protection mechanisms.